package 力扣_滑动窗口.第一类模板;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zx
 * @create 2022-05-17 16:43
 */
public class 水果成篮_904 {
    /**
     * @return 这道题的难点在于：(窗口内最多仅允许有两个不同的数字,即：篮子中最多有两种水果)
     * 自己可以想到的做法
     */
    public int totalFruit(int[] fruits) {
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        int left = 0;
        for (int right = 0; right < fruits.length; right++) {
            if(map.containsKey(fruits[right])){
                map.put(fruits[right],map.get(fruits[right]) + 1);
            }else{
                map.put(fruits[right],1);
            }
            while (map.size() > 2) {//不符合条件：水果种类大于2
                map.put(fruits[left], map.get(fruits[left]) - 1);
                if (map.get(fruits[left]) == 0){
                    map.remove(fruits[left]);
                }
                left++;  // 左边界
            }
            res = Math.max(res, right - left + 1);//更新结果
        }
        return res;
    }
    /**
     * @return 这种思路感觉自己想不到
     */
    public int totalFruit2(int[] fruits) {
        if (fruits.length <= 2){
            return fruits.length;
        }
        int res = 2;
        int left = 0;
        int count = 0;//计算篮中种类数
        //计算篮中每种水果出现的次数.提示说明了水果的种类数是有限的 0 <= fruits[i] < fruits.length
        int[] number = new int[fruits.length];
        for (int right = 0; right < fruits.length; right++) {
            number[fruits[right]] += 1; // 入篮
            if (number[fruits[right]] == 1){
                count++; //等于1说明第一次入篮,count需要加1
            }
            while (count > 2) {//篮中超过两种水果
                number[fruits[left]] -= 1;//因为下边还要使用left下标,所以先不要移动
                if (number[fruits[left]] == 0){
                    count--;//等于0说明篮中已经没有fruits[left]水果,count减1
                }
                left++;//移动left
            }
            res = Math.max(res, right - left + 1);//取窗口最大值
        }
        return res;
    }
}
